#include <stdlib.h>
#include "sort.h"

/**
 * 二分查找
 * @param nums
 * @param numsSize
 * @param goal
 * @return
 */
int search(int *nums, int numsSize, int goal) {
    int low = 0;
    int high = numsSize - 1;
    if (nums[high] < goal || nums[low] > goal) {
        return -1;
    }
    int mid;
    while (low <= high) {
        mid = (high + low) >> 1;
        if (nums[mid] > goal) {
            high = mid - 1;
        } else if (nums[mid] < goal) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

int getIndex(int *nums, int numsSize, int goal, int from) {
    for (int i = from; i < numsSize; ++i) {
        if (nums[i] == goal) {
            return i;
        }
    }
    return -1;
}

/**
 * 归并排序
 * @param nums
 * @param numsSize
 * @return
 */
int *mergeSort(int *nums, int numsSize) {
    int *temp = (int *) malloc(sizeof(int) * numsSize);
    int *copy = (int *) malloc(sizeof(int) * numsSize);
    for (int i = 0; i < numsSize; ++i) {
        copy[i] = nums[i];
    }
    sort(copy, numsSize, 0, numsSize - 1, temp);
    free(temp);
    temp = NULL;
    return copy;
}

void sort(int *nums, int numsSize, int left, int right, int *temp) {

    if (left < right) {
        int mid = (left + right) / 2;
        sort(nums, numsSize, left, mid, temp);
        sort(nums, numsSize, mid + 1, right, temp);
        merge(nums, left, mid, right, temp);
    }
}

void merge(int *nums, int left, int mid, int right, int *temp) {
    int i = left;
    int j = mid + 1;
    int index = 0;
    while (i <= mid && j <= right) {
        if (nums[i] < nums[j]) {
            temp[index++] = nums[i++];
        } else {
            temp[index++] = nums[j++];
        }
    }
    while (i <= mid) {
        temp[index++] = nums[i++];
    }
    while (j <= right) {
        temp[index++] = nums[j++];
    }
    index = 0;
    while (left <= right) {
        nums[left++] = temp[index++];
    }
}